#include "CCacheRenderer.h"
#include "CSprite.h"

#include <algorithm>
#include <cassert>

void MoveRect(SDL_Rect& r, int x, int y)
{
	r.x += x;
	r.y += y;
}

bool InspectRect(const SDL_Rect& a, const SDL_Rect& b)
{
	return !(b.x > a.x + a.w
		|| b.x + b.w < a.x
		|| b.y > a.y + a.h
		|| b.y + b.h < a.y);
}
/*
SDL_Rect IntersectRects(const SDL_Rect& a, const SDL_Rect& b)
{
	int l = std::max(a.x, b.x);
	int t = std::max(a.y, b.y);
	int r = std::min(a.x + a.w, b.x + b.w);
	int bt = std::min(a.y + a.h, b.y + b.h);

	SDL_Rect res;
	res.x = l;
	res.y = t;
	res.w = r - l;
	res.h = bt - t;

	return res;
}
*/

void CCacheRenderer::Redraw()
{
	/*
	Diff();

	std::set<int> removed;
	for (size_t i = 0; i != DiffSprites.size(); ++i)
		if (!DiffSprites[i].add)
			removed.insert(DiffSprites[i].num);

	size_t i = 0;
	size_t j = 0;
	size_t k = 0;
	SDL_Rect src;
	for (; i != SpritesOnScreen.size(); ++i)
	{
		if (j == DiffSprites.size())
			break;

		if (i == DiffSprites[j].num)
		{
			// rerender all under diff sprite:
			src = SpriteManager->Get(DiffSprites[j].t)->GetRect();
			MoveRect(src, DiffSprites[j].x, DiffSprites[j].y);
			for (; k != i; ++k)
			{
				SDL_Rect under = SpriteManager->Get(SpritesOnScreen[k].t)->GetRect();
				MoveRect(under, SpritesOnScreen[k].x, SpritesOnScreen[k].y);
				if (InspectRect(src, under))
				{
					SDL_Rect r = IntersectRects(src, under);
					if (r.w && r.h)
						RealDrawSprite(SpritesOnScreen[k].t, SpritesOnScreen[k].x, SpritesOnScreen[k].y, r);
				}
			}

			// render new sprite or render nothing
			if (DiffSprites[j].add)
				RealDrawSprite(DiffSprites[j].t, DiffSprites[j].x, DiffSprites[j].y);

			k = j;
			++j;
		}
		printf("k = %ld\n", k);
	}
	
	//*
	for (k = i; k != SpritesOnScreen.size(); ++k)
	{
		if (DiffSprites.size() != 0)
			break;

		SDL_Rect under = SpriteManager->Get(SpritesOnScreen[k].t)->GetRect();
		MoveRect(under, SpritesOnScreen[k].x, SpritesOnScreen[k].y);
		if (InspectRect(src, under))
		{
			SDL_Rect r = IntersectRects(src, under);
			if (r.w && r.h)
				RealDrawSprite(SpritesOnScreen[k].t, SpritesOnScreen[k].x, SpritesOnScreen[k].y, r);
			}
	}
	//*
	for (; j != DiffSprites.size(); ++j)
	{
		RealDrawSprite(DiffSprites[j].t, DiffSprites[j].x, DiffSprites[j].y);
	}
	*/
#if 0
	for (size_t i = 0; i != DiffSprites.size(); ++i)
	{
		if (DiffSprites[i].add)
		{
			// add this sprite
			if (DiffSprites[i].num >= SpritesOnScreen.size())
				RealDrawSprite(DiffSprites[i].t, DiffSprites[i].x, DiffSprites[i].y);
			else
			{
				SDL_Rect src = SpriteManager->Get(DiffSprites[i].t)->GetRect();
				MoveRect(src, DiffSprites[i].x, DiffSprites[i].y);
				for (size_t j = 0; j < DiffSprites[i].num; ++j)
				{
					// redraw sprite under diff sprite
					SDL_Rect under = SpriteManager->Get(SpritesOnScreen[j].t)->GetRect();
					MoveRect(under, SpritesOnScreen[j].x, SpritesOnScreen[j].y);
					if (InspectRect(src, under))
					{
						SDL_Rect r = IntersectRects(src, under);
						if (r.w && r.h)
							RealDrawSprite(SpritesOnScreen[j].t, SpritesOnScreen[j].x, SpritesOnScreen[j].y, r);
					}
				}
				RealDrawSprite(DiffSprites[i].t, DiffSprites[i].x, DiffSprites[i].y);
				printf("+ %d (%d %d,%d)\n", 
					DiffSprites[i].num,
					DiffSprites[i].t, 
					DiffSprites[i].x,
					DiffSprites[i].y);
//				j = i;
			}
		} else
		{
			// remove this sprite
			SDL_Rect src = SpriteManager->Get(DiffSprites[i].t)->GetRect();
			MoveRect(src, DiffSprites[i].x, DiffSprites[i].y);
			for (size_t j = 0; j < DiffSprites[i].num; ++j)
				{
					// redraw sprite under diff sprite
					SDL_Rect under = SpriteManager->Get(SpritesOnScreen[j].t)->GetRect();
					MoveRect(under, SpritesOnScreen[j].x, SpritesOnScreen[j].y);
					if (InspectRect(src, under))
					{
						SDL_Rect r = IntersectRects(src, under);
						if (r.w && r.h)
							RealDrawSprite(SpritesOnScreen[j].t, SpritesOnScreen[j].x, SpritesOnScreen[j].y, r);
					}
				}
		}
	}
		

		/*
	for (sprites_container::const_iterator i = SpritesOnPool.begin();
		i != SpritesOnPool.end(); ++i)
			RealDrawSprite(i->t, i->x, i->y);
			*/

//#if 0
	// printf("num_sprites = %ld\n", LastNum);
	
	if (SpritesOnPool != SpritesOnScreen)
	{
		// Need redraw screen.
		typedef std::vector<CCacheSprite> sp_cnt;
		sp_cnt diff;
		sp_cnt screen(SpritesOnScreen.begin(), SpritesOnScreen.end());
		std::set_symmetric_difference(SpritesOnPool.begin(),
			SpritesOnPool.end(),
			SpritesOnScreen.begin(),
			SpritesOnScreen.end(),
			std::back_inserter(diff));

		printf("redraw screen %ld sprites.\n", diff.size());

		ccs_cmp cmp;
		std::sort(diff.begin(), diff.end(), cmp);
		std::sort(screen.begin(), screen.end(), cmp);

		printf("[\n");
		for (sp_cnt::const_iterator i = diff.begin();
			i != diff.end();
			++i)
			if (i->on_screen)
			{
				// remove sprite from screen
				// redraw area under sprite
				printf("-%d ", i->t);
				SDL_Rect src = SpriteManager->Get(i->t)->GetRect();
				MoveRect(src, i->x, i->y);
				printf("(");
				for (sp_cnt::iterator j = screen.begin();
					j != screen.end();
					++j)
					if (*i != *j)
					{
						SDL_Rect under = SpriteManager->Get(j->t)->GetRect();
						MoveRect(under, j->x, j->y);
						if (InspectRect(src, under))
						{
							SDL_Rect r = IntersectRects(src, under);
							if (r.w && r.h)
							{
								printf("%d,%d,%d ", j->t, j->x, j->y);
								RealDrawSprite(j->t, j->x, j->y, r);
							}
						}
					}
				printf(")\n");
			}
		
		for (sp_cnt::const_iterator i = diff.begin();
			i != diff.end();
			++i)
			if (!i->on_screen)
			{
				/*
				SDL_Rect src = SpriteManager->Get(i->t)->GetRect();
				MoveRect(src, i->x, i->y);
				for (sp_cnt::iterator j = screen.begin();
					j != screen.end();
					++j)
					if (*i != *j)
					{
						SDL_Rect under = SpriteManager->Get(j->t)->GetRect();
						MoveRect(under, j->x, j->y);
						if (InspectRect(src, under))
						{
							SDL_Rect r = IntersectRects(src, under);
							if (r.w && r.h)
								RealDrawSprite(j->t, j->x, j->y, r);
						}
					}
				*/
				printf("+%d ", i->t);
				RealDrawSprite(i->t, i->x, i->y);
			}
		printf(" ]\n");
	}
#endif
	SpritesOnScreen.swap(SpritesOnPool);

	SpritesOnPool.erase(SpritesOnPool.begin(), SpritesOnPool.end());
	LastNum = 0;

	SDL_Flip(Screen);
}

void CCacheRenderer::DrawSprite(SpriteType t, size_t x, size_t y)
{
	SpritesOnPool.push_back(CCacheSprite(t, x, y, LastNum));
	++LastNum;
}

void CCacheRenderer::RealDrawSprite(SpriteType t, size_t x, size_t y)
{
	SDL_Surface* sprite = SpriteManager->Get(t)->GetSurface();
	SDL_Rect src = SpriteManager->Get(t)->GetRect();

	SDL_Rect dest;
	dest.x = TopLeftCornerMapX  + x + src.x;
	dest.y = TopLeftCornerMapY + y + src.y;
	dest.w = src.w;
	dest.h = src.h;

	SDL_BlitSurface(sprite, &src, Screen, &dest);

}

void CCacheRenderer::RealDrawSprite(SpriteType t, size_t x, size_t y, SDL_Rect& dest)
{
	SDL_Surface* sprite = SpriteManager->Get(t)->GetSurface();
//	SDL_Rect src = SpriteManager->Get(t)->GetRect();

	SDL_Rect src;
	src.x = dest.x - x;
	src.y = dest.y - y;
	src.w = dest.w;
	src.h = dest.h;

	MoveRect(dest, TopLeftCornerMapX, TopLeftCornerMapY);

	SDL_BlitSurface(sprite, &src, Screen, &dest);

}

void CCacheRenderer::PrintDiff(const int* c, size_t i, size_t j, size_t m, size_t n)
{
	if (i > 0 && j > 0 && SpritesOnScreen[i-1] == SpritesOnPool[j-1])
	{
		PrintDiff(c, i-1, j-1, m, n);
		// do nothing;
	}
	else
	{
		if (j > 0 && (i == 0 || c[(n+1)*i + j-1] >= c[(n+1)*(i-1) + j]))
		{
			PrintDiff(c, i, j-1, m, n);
			printf("+%d ", SpritesOnPool[j-1].num);
			DiffSprites.push_back(CDiffSprite(SpritesOnPool[j-1], true));

		} else if (i > 0 && (j == 0 || c[(n+1)*i + j-1] < c[(n+1)*(i-1) + j]))
		{
			PrintDiff(c, i-1, j, m, n);
			printf("-%d ", SpritesOnScreen[i-1].num);
			DiffSprites.push_back(CDiffSprite(SpritesOnScreen[i-1], false));
		}
	}
}

void CCacheRenderer::Diff()
{
	// this function compute diff of sprites_on_screen & sprites_on_pool

	DiffSprites.erase(DiffSprites.begin(), DiffSprites.end());

	const size_t size_max_buffer = 256*256;

	size_t m = SpritesOnScreen.size();
	size_t n = SpritesOnPool.size();

	assert((m + 1)*(n + 1) < size_max_buffer);

	static int c[size_max_buffer];		// create buffer on stack

	for (size_t i = 0; i < m + 1; ++i)
		c[(n + 1)*i] = 0;		// C[i,0] = 0;

	for (size_t j = 0; j < n + 1; ++j)
		c[j] = 0;				// C[0,j] = 0;

	for (size_t i = 1; i < m + 1; ++i)
		for (size_t j = 1; j < n + 1; ++j)
		{
			if (SpritesOnScreen[i - 1] == SpritesOnPool[j - 1])
				c[(n + 1)*i + j] = c[(n + 1)*(i - 1) + j - 1] + 1;
			else
				c[(n + 1)*i + j] = std::max(c[(n + 1)*i + j - 1], c[(n+1)*(i-1) + j]);
		}

	PrintDiff(c, m, n, m, n);
}